package com.cy.linklist;

import java.util.HashSet;

/**
 * @Author: chenyun
 * @Date: 2021/09/17/15:30
 * @Description:
 */

// 力扣 141题  判定链表是否有环

public class Demo141 {

    // 解法1 快慢指针  如果是一个环，跑到快的一点会追上跑到慢的
    public static boolean hasCycle1(ListNode head) {
        ListNode s = head, f = head;  // s慢指针  f快指针
        while(f != null && f.next != null){
            s = s.next;  // 慢指针跑到慢
            f = f.next.next;    // 快指针跑到快
            if(s == f) return true;     // 快追上慢有环
        }
        return false;
    }


    // 解法2  每次遍历到一个节点时，判断该节点此前是否被访问过
    // 将未访问的点放入HashSet  HashSet已经存在的点再放入时add返回的值为false
    public static boolean hasCycle2(ListNode head) {
        HashSet<ListNode> set = new HashSet<>(); // 存储已经访问过的节点
        while (head != null){
            if(!set.add(head)){ //如果set里没有add返回值为true   如果set里有返回值为false
                return true;
            }
            head = head.next;
        }
        return false;
    }

    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("1");
        set.add("2");
        set.add("3");
        System.out.println(set.add("3"));

    }
}
